package com.lhcai.lc.category.matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 *
 * @author liuhuaicai
 * @since 2025-01-04 11:13
 */
public class Lc54 {
    public static void main(String[] args) {
        Lc54 lc54 = new Lc54();
        System.out.println(lc54.spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int count = m * n;
        List<Integer> res = new ArrayList<>();
        // 方向映射 西南东北
        int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 初始方向
        int cur = 0;
        int x = 0;
        int y = 0;
        boolean[][] flag = new boolean[m][n];
        for (int i = 0; i < count; i++) {
            res.add(matrix[x][y]);
            flag[x][y] = true;
            int nextX = x + dir[cur][0];
            int nextY = y + dir[cur][1];
            if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n || flag[nextX][nextY]) {
                cur = (cur + 1) % 4;
            }
            x += dir[cur][0];
            y += dir[cur][1];
        }
        return res;
    }

    // 行、列处理，缩小内径
//    public List<Integer> spiralOrder(int[][] matrix) {
//        int m = matrix.length;
//        int n = matrix[0].length;
//        // 记录路径
//        List<Integer> res = new ArrayList<>();
//        // 记录边界
//        int rowStart = 0;
//        int colStart = 0;
//        int rowEnd = m - 1;
//        int colEnd = n - 1;
//        while (rowStart <= rowEnd && colStart <= colEnd) {
//            // 首行,列正序，到最右
//            for (int i = colStart; i <= colEnd; i++) {
//                res.add(matrix[rowStart][i]);
//            }
//            // 尾列，行正序，到最下
//            for (int i = rowStart + 1; i <= rowEnd; i++) {
//                res.add(matrix[i][colEnd]);
//            }
//            // 只有行列都不重叠的时候，才需要进行尾行，首列的遍历
//            if (rowStart < rowEnd && colStart < colEnd) {
//                // 尾行，列倒序，到最左
//                for (int i = colEnd - 1; i >= colStart; i--) {
//                    res.add(matrix[rowEnd][i]);
//                }
//                // 首列，行倒序
//                for (int i = rowEnd - 1; i >= rowStart + 1; i--) {
//                    res.add(matrix[i][colStart]);
//                }
//            }
//            rowStart += 1;
//            colStart += 1;
//            rowEnd -= 1;
//            colEnd -= 1;
//        }
//        return res;
//    }
}
